#include <bits/stdc++.h>
#include <ranges>
using namespace std;
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */

// 法一
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
right(right) {}
};

class Solution {
	public:
	TreeNode* reverseOddLevels(TreeNode* root) {
		if (!root)
			return nullptr;
		queue<TreeNode*> q;
		q.push(root);
		int level = 0;
		while (!q.empty()) {
			int size = q.size();
			vector<TreeNode*> nodeAtLevel;
			vector<int> valAtLevel;
			// 当前层的所有节点
			for (int i = 0; i < size; i++) {
				TreeNode* node = q.front();
				q.pop();
				// 奇数层 记录节点
				if (level % 2 == 1) {
					nodeAtLevel.push_back(node);
					valAtLevel.push_back(node->val);
				}
				// 将孩子节点加入队列
				if (node->left)
					q.push(node->left);
				if (node->right)
					q.push(node->right);
			}
			// 奇数层还要反转
			if (level % 2 == 1) {
				int n = valAtLevel.size();
				for (int i = 0; i < n; i++) {
					nodeAtLevel[i]->val = valAtLevel[n - 1 - i];
				}
			}
			level++;
		}
		return root;
	}
};
// 法二
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
	public:
	TreeNode* reverseOddLevels(TreeNode* root) {
		vector<TreeNode*> pre;  // 存储上一层的节点
		vector<TreeNode*> cur{root};  // 当前层的节点，从根节点开始
		int depth = 0;  // 当前层的深度，初始为0

		while (!cur.empty()) {  // 当当前层节点不为空时
			++depth;  // 进入下一层，增加深度
			vector<TreeNode*> nxt;  // 用于存储下一层的节点

			// 遍历当前层的每个节点，构建下一层的节点
			for (auto node : cur) {
				if (node) {
					if (node->left)
						nxt.push_back(node->left);  // 将左子节点加入下一层
					if (node->right)
						nxt.push_back(node->right);  // 将右子节点加入下一层
				} else {
					nxt.push_back(nullptr);  // 如果当前节点为空，则在下一层添加空节点
					nxt.push_back(nullptr);  // 继续添加空节点以保持节点对齐
				}
			}

			// 如果当前层是偶数层（从1开始，偶数层需要反转）
			if (depth % 2 == 0) {
				std::reverse(cur.begin(), cur.end());  // 反转当前层的节点顺序
				// 更新上一层节点的子节点指向当前层的节点
				for (int i = 0; i < pre.size(); i++) {
					auto node = pre[i];
					if (node) {
						node->left = cur[2 * i];  // 更新左子节点
						node->right = cur[2 * i + 1];  // 更新右子节点
					}
				}

				// 如果下一层不为空，更新下一层的节点
				if (!nxt.empty()) {
					for (int i = 0; i < cur.size(); i++) {
						auto node = cur[i];
						if (node) {
							node->left = nxt[i * 2];  // 更新左子节点
							node->right = nxt[i * 2 + 1];  // 更新右子节点
						}
					}
				}
			}

			// 将当前层节点移到上一层，准备下一轮迭代
			pre = move(cur);
			cur = move(nxt);  // 下一层节点作为当前层
		}

		return root;  // 返回修改后的根节点
	}
};